package com.zh.note.leetcode.greedy;

import java.util.*;

/**
 * 56. 合并区间
 * <p>
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 */
public class LC_56_merge {
    public static int[][] merge(int[][] intervals) {
        Deque<int[]> res = new LinkedList<>();
        if (intervals == null || intervals.length == 0) {
            return null;
        }
        // 按照第一个元素
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        // 相当于把[1,3] 加入了
        res.addLast(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            //res.getLast()获取的就是上一个区间
            if (intervals[i][0] <= res.getLast()[1]) { // 发生重叠
                // 更新右边界
                res.getLast()[1] = Math.max(intervals[i][1], res.getLast()[1]);
            } else {
                // 没有重叠
                res.addLast(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);

    }

    public static void main(String[] args) {
        int[][] nums = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        System.out.println(merge(nums));
    }
}
